home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / hashf.cq / hashf.c
Encoding:
Text File  |  1986-03-13  |  12.7 KB  |  569 lines
  1. S 2
  2.  
  3.  
  4. Type P to Pause, S to Stop listing
  5.  
  6. cat puppy.c
  7. # include <stdio.h>
  8.  
  9. long hash();
  10.  
  11. main()
  12. {
  13.     char cmd[16], key[1024], content[1024], fname[100], *bptr;
  14.     int filedesc, mode, size, keysize, contsize, depth;
  15.     long offset;
  16.  
  17.     while (1) {
  18.     printf("? "); 
  19.     gets(cmd);
  20.     switch (cmd[0]) {
  21.     case '?':
  22.         printf("create open klose read write find delete seq hash\n");
  23.         break;
  24.     case 'c':
  25.         printf("Name? "); 
  26.         gets(fname);
  27.         printf("Mode? "); 
  28.         scanf("%d", &mode); 
  29.         getchar();
  30.         printf("Size? "); 
  31.         scanf("%d", &size); 
  32.         getchar();
  33.         filedesc = hcreate(fname, mode, size);
  34.         if (filedesc == -1) printf("Failed\n");
  35.         else printf("Filedesc = %d\n", filedesc);
  36.         break;
  37.     case 'o':
  38.         printf("Name? "); 
  39.         gets(fname);
  40.         printf("Mode? "); 
  41.         scanf("%d", &mode); 
  42.         getchar();
  43.         filedesc = hopen(fname, mode);
  44.         if (filedesc == -1) printf("Failed\n");
  45.         else printf("Filedesc = %d\n", filedesc);
  46.         break;
  47.     case 'k':
  48.         printf("Filedesc? "); 
  49.         scanf("%d", &filedesc); 
  50.         getchar();
  51.         filedesc = hclose(filedesc);
  52.         if (filedesc == -1) printf("Failed\n");
  53.         break;
  54.     case 'r':
  55.         printf("Filedesc? "); 
  56.         scanf("%d", &filedesc); 
  57.         getchar();
  58.         printf("Key? "); 
  59.         gets(key);
  60.         keysize = strlen(key);
  61.         contsize = sizeof(content);
  62.         bptr = content;
  63.         contsize = hread(filedesc, key, keysize, content, contsize);
  64.         if (contsize == -1) printf("Failed");
  65.         else if (contsize > sizeof(content)) printf("Too big");
  66.         else while (contsize--) putchar(*bptr++);
  67.         putchar('\n');
  68.         break;
  69.     case 'w':
  70.         printf("Filedesc? "); 
  71.         scanf("%d", &filedesc); 
  72.         getchar();
  73.         printf("Key? "); 
  74.         gets(key);
  75.         keysize = strlen(key);
  76.         printf("Content? "); 
  77.         gets(content);
  78.         contsize = strlen(content);
  79.         contsize = hwrite(filedesc, key, keysize, content, contsize);
  80.         if (contsize == -1) printf("Failed\n");
  81.         break;
  82.     case 'd':
  83.         printf("Filedesc? "); 
  84.         scanf("%d", &filedesc); 
  85.         getchar();
  86.         printf("Key? "); 
  87.         gets(key);
  88.         keysize = strlen(key);
  89.         contsize = hdelete(filedesc, key, keysize);
  90.         if (contsize == -1) printf("Failed\n");
  91.         break;
  92.     case 'f':
  93.         printf("Filedesc? "); 
  94.         scanf("%d", &filedesc); 
  95.         getchar();
  96.         printf("Key? "); 
  97.         gets(key);
  98.         keysize = strlen(key);
  99.         contsize = hfind(filedesc, key, keysize, &bptr);
  100.         if (contsize == -1) printf("Failed");
  101.         else while (contsize--) putchar(*bptr++);
  102.         putchar('\n');
  103.         break;
  104.     case 's':
  105.         printf("Filedesc? "); 
  106.         scanf("%d", &filedesc); 
  107.         getchar();
  108.         printf("Offset(hex)? "); 
  109.         scanf("%X", &offset); 
  110.         getchar();
  111.         keysize = hseq(filedesc, &bptr, &offset);
  112.         if (keysize == -1) printf("Failed\n");
  113.         else {
  114.         printf("New offset = %x\n", offset);
  115.         while (keysize--) putchar(*bptr++);
  116.         putchar('\n');
  117.         }
  118.         break;
  119.     case 'h':
  120.         printf("Key? "); 
  121.         gets(key);
  122.         printf("Depth? "); 
  123.         scanf("%d", &depth); 
  124.         getchar();
  125.         printf("Hash(hex) = %X\n", hash(key, strlen(key), depth));
  126.         break;
  127.     default:
  128.         printf("Enter ? for help\n");
  129.         break;
  130.     }
  131.     }
  132. }
  133. % cap off
  134. cap: 
  135. Command not found.
  136. % 
  137. Type Selection or M for list, 
  138. P to set protocol, <CR> to exit: 
  139. 1
  140.  
  141.  
  142. Type P to Pause, S to Stop listing
  143.  
  144. cat hashf.c
  145. /*        H A S H F  L I B R A R Y
  146.  
  147.     Accesses data using (key,content) pairs stored in external files.
  148.     Copyright 1985 John Cowan; all rights reserved.
  149.     Permission granted for reproduction in non-commercial uses.
  150.  
  151.     This version has the following data-type dependencies:
  152.     Long must be 4 characters long (32 bits).
  153.     Short must be 2 characters long (16 bits).
  154.     Int may be either.
  155.     Key and buffer sizes are limited by the size of Short.
  156.     File sizes (in bytes) are limited by the size of Long.
  157. */
  158.  
  159. # define FDS 20        /* max number of open files system allows */
  160. static int fd;
  161.  
  162. static struct    {            /* all disk stuff is long for portability */
  163.     long _magic;        /* magic number on disk, open flag in core */
  164.     long _freeblk;        /* pointer to available free block */
  165.     long _bsize;        /* block size of .dat file */
  166.     long _cur;        /* currently resident .dat block, -1 on disk */
  167.     long _len;        /* length of .dat file */
  168.     long _depth;        /* depth of .idx file */
  169.     /* Remaining stuff is meaningless on disk */
  170.     int _idxfd;        /* fd of .idx file */
  171.     char *_block;        /* .dat block buffer */
  172. } 
  173. _header[FDS];
  174.  
  175. # define Header _header[fd]
  176. # define Magic Header._magic
  177. # define Bsize Header._bsize
  178. # define Freeblk Header._freeblk
  179. # define Cur Header._cur
  180. # define Idxfd Header._idxfd
  181. # define Block Header._block
  182. # define Len Header._len
  183. # define Depth Header._depth
  184.  
  185. # define DEFAULT 10        /* default to 1024-byte .dat block size */
  186. # define SETFD \
  187. if (fd = ufd, fd < 0 || fd >= FDS || Magic != DATmagic) \
  188.         return(-1)
  189. # define DATmagic 6460        /* "DAT" in RAD50 */
  190. # define BUFFER(x) (char *)(&x)
  191. # define NONNULL(x) if ((x) == 0) return(-1);
  192.  
  193. # define GETVAL(p) (_t_ = *(p) , _t_+((p)[1]<<8))
  194. # define PUTVAL(p,i) (*(p) = i&0xFF , (p)[1] = i>>8)
  195. static int _t_;
  196.  
  197. # define WALK(b,k,ks,c,cs) \
  198. (ks=GETVAL(b), b+=2, k=b, b+=ks, cs=GETVAL(b), b+=2, c=b, b+=cs)
  199.  
  200. char *strcpy(), *strcat(), *malloc();
  201. long lseek(), hash(), balloc(), getidx();
  202.  
  203. int hcreate(fname, mode, size)
  204. char *fname;
  205. int mode;
  206. int size;
  207. {
  208.     char lname[100];
  209.  
  210.     strcpy(lname, fname);
  211.     if (strlen(fname) > sizeof(lname)) return(-1);
  212.     strcat(lname, ".idx");
  213.     fd = creat(lname, mode);
  214.     if (size == 0) size = DEFAULT;
  215.     if (size < 7) size = 7;
  216.     if (size > 15) return(-1);
  217.     Bsize = 1<<size;
  218.     write(fd, BUFFER(Bsize), 4);
  219.     close(fd);
  220.     strcpy(lname, fname);
  221.     strcat(lname, ".dat");
  222.     fd = creat(lname, mode);
  223.     Magic = DATmagic;
  224.     Freeblk = 0;
  225.     Len = Bsize;
  226.     Depth = 0;
  227.     balloc();        /* also writes out header */
  228.     close(fd);
  229.     Magic = 0;
  230.     return(hopen(fname, 2));
  231. }
  232.  
  233. int hopen(fname, mode)
  234. char *fname;
  235. int mode;
  236. {
  237. # define OPENFAIL {hclose(fd); return(-1);}
  238.     char lname[100];
  239.     extern char *malloc();
  240.  
  241.     if (strlen(fname) > sizeof(lname)) return(-1);
  242.     strcpy(lname, fname);
  243.     strcat(lname, ".dat");
  244.     fd = open(lname, mode);
  245.     read(fd, BUFFER(Header), sizeof(Header));
  246.     if (Magic != DATmagic) OPENFAIL
  247.     strcpy(lname, fname);
  248.     strcat(lname, ".idx");
  249.     Idxfd = open(lname, mode);
  250.     if (Idxfd == -1) OPENFAIL
  251.  
  252.     Cur = -1;
  253.     Block = malloc((unsigned)Bsize);
  254.     if (Block == 0) OPENFAIL
  255.     return(fd);
  256. }
  257.  
  258. hclose(ufd)
  259. int ufd;
  260. {
  261.     SETFD;
  262.     close(fd);
  263.     close(Idxfd);
  264.     if (Block) free(Block);
  265.     Magic = 0;
  266.     return(0);
  267. }
  268.  
  269. int hread(ufd, key, keysize, buff, buffsize)
  270. int ufd;
  271. char *key;
  272. int keysize;
  273. char *buff;
  274. int buffsize;
  275. {
  276.     char *content;
  277.     int contsize;
  278.     register i;
  279.  
  280.     contsize = hfind(ufd, key, keysize, &content);
  281.     if (contsize > 0)
  282.     for (i=0; i < buffsize && i < contsize; i++)
  283.         buff[i] = content[i];
  284.     return (contsize);
  285. }
  286.  
  287. int hfind(ufd, key, keysize, pcontent)
  288. int ufd;
  289. char *key;
  290. int keysize;
  291. char **pcontent;
  292. {
  293.     int contsize;
  294.  
  295.     SETFD; 
  296.     NONNULL(keysize);
  297.     load(getidx(hash(key, keysize, (int)Depth)));
  298.     contsize = search(key, keysize, pcontent);
  299.     return(contsize);
  300. }
  301.  
  302. int hdelete(ufd, key, keysize)
  303. int ufd;
  304. char *key;
  305. int keysize;
  306. {
  307.     char *content;
  308.  
  309.     SETFD; 
  310.     NONNULL(keysize);
  311.     load(getidx(hash(key, keysize, (int)Depth)));
  312.     if (search(key, keysize, &content) == -1) return(-1);
  313.     zap();
  314.     return(rewrite());
  315. }
  316.  
  317. int hwrite(ufd, key, keysize, buff, buffsize)
  318. int ufd;
  319. char *key;
  320. int keysize;
  321. char *buff;
  322. int buffsize;
  323. {
  324.     char *content;
  325.  
  326.     SETFD; 
  327.     NONNULL(keysize); 
  328.     NONNULL(buffsize);
  329.     if (keysize + buffsize + 7 > Bsize) return(-1);
  330.     while (1) {
  331.     load(getidx(hash(key, keysize, (int)Depth)));
  332.     if (search(key, keysize, &content) != -1) zap();
  333.     if (jam(Block, key, keysize, buff, buffsize) != -1) {
  334.         return(rewrite());
  335.     }
  336.     split();
  337.     }
  338. }
  339.  
  340. int hseq(ufd, pkey, poffset)
  341. int ufd;
  342. char **pkey;
  343. long *poffset;
  344. # define Offset *poffset
  345. {
  346.     long himask = ~(Bsize - 1);
  347.     long lomask = Bsize - 1;
  348.     char *blk;
  349.     char *dummy;
  350.     int keysize, dummysize;
  351.  
  352.     SETFD;
  353.     if (Offset == 0) Offset = Bsize;
  354.     blk = Block + (Offset & lomask);
  355.     Offset &= himask;
  356.     if(load(Offset) == -1) return(-1);
  357.     WALK(blk, (*pkey), keysize, dummy, dummysize);
  358.     Offset += GETVAL(blk) ? blk - Block : Bsize;
  359.     return (keysize);
  360. }
  361.  
  362. # define KNUTH 1327217885
  363.  
  364. static unsigned long rotate(i)
  365. unsigned long i;
  366. {
  367.     int bit;
  368.  
  369.     bit = (i & 0x80000000);
  370.     if (bit) i &= 0x7FFFFFFF;
  371.     return((i << 1) + bit);
  372. }
  373.  
  374. long hash(s, len, depth)
  375. char *s;
  376. int len;
  377. int depth;
  378. {
  379.     unsigned long accum = 0;
  380.     long item = 0;
  381.     int shift = 0;
  382.     int i;
  383.  
  384.     for (i=0; i<len; i++) {
  385.     item = (item<<6) + s[i];
  386.     if (++shift == 5) {
  387.         accum = rotate(accum) ^ item;
  388.         item = shift = 0;
  389.     }
  390.     }
  391.     if (shift) accum = rotate(accum) ^ item;
  392.  
  393.     accum *= KNUTH;
  394.     accum = accum >> (32 - depth);
  395.     return (accum);
  396. }
  397.  
  398.  
  399. static load(offset)
  400. long offset;
  401. {
  402.     if (Cur != offset) {
  403.     Cur = offset;
  404.     lseek(fd, Cur, 0);
  405.     if (read(fd, Block, (int)Bsize) == 0) return(-1);
  406.     }
  407.     return(0);
  408. }
  409.  
  410. static int rewrite()
  411. {
  412.     lseek(fd, Cur, 0);
  413.     return((write(fd, Block, (int)Bsize) == -1) ? -1 : 0);
  414. }
  415.  
  416. static long balloc()
  417. {
  418.     long newblk;
  419.     long zero = 0L;
  420.  
  421.     newblk = Len;
  422.     Len += Bsize;
  423.     lseek(fd, Len-4, 0);
  424.     write(fd, BUFFER(zero), 4);
  425.     lseek(fd, newblk, 0);
  426.     write(fd, BUFFER(zero), 4);
  427.     lseek(fd, 0L, 0);
  428.     write(fd, BUFFER(Header), sizeof(Header));
  429.     return(newblk);
  430. }
  431.  
  432. static char *zapmark;
  433.  
  434. static int same(dst, dlen, src, slen)
  435. char *dst, *src;
  436. int dlen, slen;
  437. {
  438.     if (dlen != slen) return(0);
  439.     while (dlen--)
  440.     if (*dst++ != *src++) return(0);
  441.     return(1);
  442. }
  443.  
  444. static int search(key, keysize, pcontent)
  445. char *key;
  446. int keysize;
  447. char **pcontent;
  448. {
  449.     char *blk = Block;
  450.     char *bkey, *cont;
  451.     int bkeysize, contsize;
  452.  
  453.     while (GETVAL(blk)) {
  454.     zapmark = blk;
  455.     WALK(blk, bkey, bkeysize, cont, contsize);
  456.     if (same(key, keysize, bkey, bkeysize)) {
  457.         *pcontent = cont;
  458.         return (contsize);
  459.     }
  460.     }
  461.     return(-1);
  462. }
  463.  
  464. static int zap()
  465. {
  466.     char *zapsrc = zapmark;
  467.     char *key, *cont;
  468.     int size, keysize, contsize;
  469.  
  470.     WALK(zapsrc, key, keysize, cont, contsize);
  471.     while (size = GETVAL(zapsrc)) {
  472.     PUTVAL(zapmark, size);
  473.     zapsrc += 2;
  474.     zapmark += 2;
  475.     while (size--) *zapmark++ = *zapsrc++;
  476.     }
  477.     PUTVAL(zapmark, 0);
  478.     return(GETVAL(Block) == 0);
  479. }
  480.  
  481. static int jam(blk, key, keysize, buff, buffsize)
  482. char *blk, *key, *buff;
  483. int keysize, buffsize;
  484. {
  485.     int size;
  486.     char *blk0;
  487.  
  488.     blk0 = blk;
  489.     while (size = GETVAL(blk)) blk += size + 2;
  490.     if ((blk - blk0) + keysize + buffsize + 7 > Bsize) return(-1);
  491.     /* 2 length words, zero word, r-byte at end of block */
  492.     PUTVAL(blk, keysize);
  493.     blk += 2;
  494.     while (keysize--) *blk++ = *key++;
  495.     PUTVAL(blk, buffsize);
  496.     blk += 2;
  497.     while (buffsize--) *blk++ = *buff++;
  498.     PUTVAL(blk, 0);
  499.     return(0);
  500. }
  501.  
  502. static long getidx(offset)
  503. long offset;
  504. {
  505.     lseek(Idxfd, offset, 0);
  506.     read(Idxfd, BUFFER(offset), 4);
  507.     return(offset);
  508. }
  509.  
  510. # define R Block[Bsize-1]
  511. # define R0 new0[Bsize-1]
  512. # define R1 new1[Bsize-1]
  513.  
  514. static split()
  515. {
  516.     char *new0, *new1;
  517.     long mask, hval, start, finish, i, newblk;
  518.     char *blk = Block;
  519.     int keysize, contsize;
  520.     char *key, *content;
  521.  
  522.     if (R == Depth) expand();
  523.     new0 = malloc((unsigned)Bsize);
  524.     PUTVAL(new0, 0);
  525.     new1 = malloc((unsigned)Bsize);
  526.     PUTVAL(new1, 0);
  527.     mask = 1 << (Depth - ++R);
  528.     while (GETVAL(blk)) {
  529.     WALK(blk, key, keysize, content, contsize);
  530.     hval = hash(key, keysize, (int)Depth);
  531.     if (hval & mask)
  532.         jam(new1, key, keysize, content, contsize);
  533.     else
  534.         jam(new0, key, keysize, content, contsize);
  535.     }
  536.     R0 = R1 = R;
  537.     lseek(fd, Cur, 0);
  538.     write(fd, new0, (int)Bsize);
  539.     newblk = balloc();
  540.     lseek(fd, newblk, 0);
  541.     write(fd, new1, (int)Bsize);
  542.     Cur = -1;
  543.     start = (hval & ~(mask - 1)) | mask;
  544.     finish = start + mask;
  545.     for (i = start; i < finish; i++) {
  546.     lseek(Idxfd, i*4, 0);
  547.     write(Idxfd, BUFFER(newblk), 4);
  548.     }
  549. }
  550.  
  551. static expand()
  552. {
  553.     int idxlen = 1<<Depth;
  554.     long entry[2];
  555.     long register i;
  556.  
  557.     for (i=idxlen-1; i>=0; i--) {
  558.     lseek(Idxfd, i*4, 0);
  559.     read(Idxfd, BUFFER(entry[0]), 4);
  560.     entry[1] = entry[0];
  561.     lseek(Idxfd, i*8, 0);
  562.     write(Idxfd, BUFFER(entry[0]), 8);
  563.     }
  564.     Depth++;
  565. }
  566. % 
  567. Type Selection or M for list, 
  568. P to set protocol, <CR> to exit: 
  569.